// 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

// 示例 1:

// 输入:
// A: [1,2,3,2,1]
// B: [3,2,1,4,7]
// 输出: 3
// 解释: 
// 长度最长的公共子数组是 [3, 2, 1]。
// 说明:

// 1 <= len(A), len(B) <= 1000
// 0 <= A[i], B[i] < 100

#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

// 动态规划
// 时间复杂度：O(MN)
// 空间复杂度：O(MN)
// dp(A[i], B[j]) = dp(A[i+1], B[j+1]) + 1 // A[i-1] == B[j-1]
// dp(A[i], B[j]) = 0                      // A[i-1] != B[j-1]
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int res{0};
        int m = A.size();
        int n = B.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i{m - 1}; i >= 0; ++i) {
            for (int j{n - 1}; j >= 0; ++j) {
                dp[i][j] = (A[i] == B[j] ? dp[i+1][j+1] + 1 : 0);
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

// 滑动窗口
// 对齐开始位置
// 时间复杂度：O((MN) * min(M, N))
// 空间复杂度：O(1)
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size();
        int m = B.size();
        int res{0};
        for (int i{0}; i < n; ++i) {
            int len = min(m, n - i);
            int maxLen = maxLength(A, B, i, 0, len);
            res = max(res, maxLen);
        }
        for (int i{0}; i < m; ++i) {
            int len = min(n, m - i);
            int maxLen = maxLength(A, B, 0, i, len);
            res = max(res, maxLen);
        }
        return res;
    }
    int maxLength(vector<int>& A, vector<int>& B, int indexA, int indexB, int len) {
        int res{0};
        int k{0};
        for (int i{0}; i < len; ++i) {
            if (A[indexA + i] == B[indexB + i]) ++k;
            else k = 0;
            res = max(res, k);
        }
        return res;
    }
};

// 二分查找 + 哈希
// 如果数组 A 和 B 有一个长度为 k 的公共子数组，
// 那么它们一定有长度为 j <= k 的公共子数组。这样我们可以通过二分查找的方法找到最大的 k。
// 时间复杂度：O((M + N) log(min(M, N)))
// 空间复杂度：O(N)
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int left{1};
        int right = min(A.size(), B.size()) + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(A, B, mid)) left = mid + 1;
            else right = mid;
        }
        return left - 1;
    }
    bool check(vector<int>& A, vector<int>& B, int len) {
        long long hashA{0};
        for (int i{0}; i < len; ++i) {
            hashA = (hashA * base + A[i]) % mod;
        }
        unordered_set<long long> bucketA{};
        bucketA.insert(hashA);
        long long mult = qPow(base, len - 1);
        for (int i{len}, n = A.size(); i < n; ++i) {
            hashA = ((hashA - A[i - len] * mult % mod + mod) % mod * base + A[i]) % mod;
            bucketA.insert(hashA);
        }
        long long hashB{0};
        for (int i{0}; i < len; ++i) {
            hashB = (hashB * base + B[i]) % mod;
        }
        if (bucketA.count(hashB)) return true;
        for (int i{len}, n = B.size(); i < n; ++i) {
            hashB = ((hashB - B[i - len] * mult % mod + mod) % mod * base + B[i]) % mod;
            if (bucketA.count(hashB)) return true;
        }
        return false;
    }
    // 使用快速幂计算 x^n % mod 的值
    long long qPow(long long x, long long n) {
        long long res{1};
        while (n) {
            if (n & 1) res = res * x % mod;
            x = x * x % mod;
            n /= 2;
        }
        return res;
    }
private:
    const int mod{1000000009};
    const int base{113};
};